import javax.swing.*;
import java.util.*;
import java.awt.*;

/*
    通过使用栈来规避递归，解决迷宫的生成。
*/




public class Main extends JFrame
{

    static int row = 67;//迷宫行数
    static int col = 67;//迷宫列数
    static int PaneSize = 10;

    static int width = PaneSize * row;
    static int height = PaneSize * col;

    //二维数组，迷宫的地图
    static int[][] Map = new int[row][col];

    //记录走过的路点
    static Stack<loca> st = new Stack<>();

    static ArrayList<loca> path = new ArrayList<loca>();
    static ArrayList<loca> result = new ArrayList<loca>();

    //函数声明：
    //声明失败

    class loca
    {
        loca(int x, int y)
        {
            this.x = x;
            this.y = y;
        }

        int x;
        int y;
    }


    @Override
    public void paint(Graphics g)
    {


        for(int i = 0;i<row;i++)
        {
            for(int j = 0;j<col;j++)
            {
                if(Map[i][j] == 0)
                {
                    g.setColor(Color.white);
                    g.fillRect(i*PaneSize,j*PaneSize,PaneSize,PaneSize);
                }
                else if(Map[i][j] == 1)
                {
                    g.setColor(Color.BLACK);
                    g.fillRect(i*PaneSize,j*PaneSize,PaneSize,PaneSize);
                }
            }
        }

        g.setColor(Color.BLUE);

        for(int i = 0;i<width;i+=PaneSize)
        {
            int x1 = 0;
            int y1 = i;

            int x2 = width;
            int y2 = y1;

            g.drawLine(x1,y1,x2,y2);
            g.drawLine(i,0,i,height);
        }





        //睡眠两秒出答案
        try {
            Thread.sleep(2000);
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }

        for(int i = 0;i<result.size();i++)
        {
            int x = result.get(i).x;
            int y = result.get(i).y;

            g.setColor(Color.red);
            g.fillRect(x*PaneSize,y*PaneSize,PaneSize,PaneSize);

//            //睡眠
//            try {
//                Thread.sleep(200);
//            } catch (InterruptedException e) {
//                throw new RuntimeException(e);
//            }
        }

    }



    void launch()
    {
        this.getContentPane().setBackground(new Color(195, 184, 162)); // 设置窗体背景颜色
        this.setSize(width,height);
        this.setUndecorated(true);// 取消窗体修饰效果
        this.setAlwaysOnTop(true); //窗体最顶层显
        this.setLocationRelativeTo(null);//窗口在屏幕中间显示

        //画 row - 1 条线
        //
        
        this.setVisible(true);
    }

    void init()
    {
        //初始化为墙
        for(int i = 0;i<row;i++)
        {
            for(int j = 0;j<col;j++)
            {
                Map[i][j] = 1;//1表示墙，0表示路
            }
        }
    }



    //
    void create(int i,int j){

        //第一个路点是 (1,1)
        Map[1][1] = 0;
        st.push(new loca(1,1));


        //定义数组来保存周围的路点
        ArrayList<loca> list = new ArrayList<>();

        while(!st.empty())
        {
            // 1 没有选择的路点，一直回溯到有，或者为空
            while(!HaveRoadPint(i,j,list) && !st.empty())
            {
                loca tmp = st.pop();

                i = tmp.x;
                j = tmp.y;
            }

            //说明遍历完了所有路点，不需要再继续了
            if(st.empty())
            {
                break;
            }

            // 2 从能选的路点里 随机 选一个

            //来到这里说明周围有路点了
            Random rd = new Random();
            int idx = rd.nextInt(list.size());


            int x = list.get(idx).x;
            int y = list.get(idx).y;

            Map[x][y] = 0;
            st.push(new loca(x,y));


            // 3 将选择的路点 (x,y) 和 (i,j) 打通


            through(x,y,i,j);



            list.clear();

        }

    }


    //打通两个路点的墙壁
    void through(int x , int y, int i ,int j)
    {
        if(x == i)
        {
            Map[x][(y+j)/2] = 0;
        }
        else if(y == j)
        {
            Map[(x+i)/2][j] = 0;
        }
    }


    //检查周围是否有路点,有顺便保存
    boolean HaveRoadPint(int i , int j,ArrayList<loca> list)
    {
        if(i-2 > 0 && Map[i-2][j] == 1)
        {
            list.add(new loca(i-2,j));
        }

        if(i+2 < row && Map[i+2][j] == 1)
        {
            list.add(new loca(i+2,j));

        }

        if(j-2 > 0 && Map[i][j-2] == 1)
        {
            list.add(new loca(i,j-2));
        }

        if(j+2 < col && Map[i][j+2] == 1)
        {
            list.add(new loca(i,j+2));
        }


        return !list.isEmpty();
    }




    void FindPath(int i,int j)
    {
        //3表示已经走过
        Map[i][j] = 3;
        path.add(new loca(i,j));

        if(i == row-2 && j == col-2)
        {
            result = new ArrayList<>(path);
            return;
        }

        //四个方向探测
        if(i-1 > 0 && Map[i-1][j] == 0)
        {
            FindPath(i-1,j);
        }
        if(i+1 < row && Map[i+1][j] == 0)
        {
            FindPath(i+1,j);
        }
        if(j-1 > 0 && Map[i][j-1] == 0)
        {
            FindPath(i,j-1);
        }
        if(j+1 < col && Map[i][j+1] == 0)
        {
            FindPath(i,j+1);
        }


        //0表示路
        Map[i][j] = 0;
        path.remove(path.size()-1);
    }



    static void Print()
    {
        for(int i = 0;i<row;i++)
        {
            for(int j = 0;j<col;j++)
            {
                System.out.print(Map[i][j] + " ");
            }
            System.out.println();
        }

        System.out.println();
    }


    public static void main(String[] args){

        //初始化迷宫
        new Main().init();
        Print();

        //创建迷宫
        new Main().create(1,1);
        Print();

        //寻路
        new Main().FindPath(1,1);

        for(int i = 0;i<result.size();i++)
        {
            System.out.println("(" + result.get(i).x + "," + result.get(i).y + ")");
        }

        //图形化
        new Main().launch();

    }

    void sleep(int mtime)
    {

        //睡眠
        try {
            Thread.sleep(mtime);
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }



}